package DoublePointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class Solution {
    // 双指针专题
    public int triangleNumber(int[] nums) {
        // 第一种暴力枚举
        //第二种解法利用单调性使用双指针算法
        Arrays.sort(nums);
        int ans =0;

        for (int i = nums.length-1; i >= 0 ; i--) {
            int left =0 , right = i-1;
            while (left < right){
                if (nums[left] + nums[right] > nums[i]){
                    ans+=right-left;
                    right--;
                }else {
                    left++;
                }
            }
        }
        return ans;
    }
    public static List<List<Integer>> threeSum(int[] nums) {
    // 解法1 排序+暴力枚举+set去重
    // 解法2 (如果数组有序-就想二分或双指针) 排序+双指针
        // ①排序 ②固定一个数A.③在后序的区间利用双指针找到 -a
        // 细节 : 去重(利用left和right指针跳过重复的元素) 并且第一个原数组也要跳过重复的元素
        // 不漏(找到一种结果,不停缩小区间,继续寻找)
        List<List<Integer>> ans = new LinkedList<>();
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < len; ) {
            int cur = nums[i];
            if (cur > 0)break;
            int left =i+1 ,right =len-1;
            while (left < right){
                int sum = nums[left] + nums[right];
                if (sum == -cur){
                    ans.add(new ArrayList<>(Arrays.asList(nums[i],nums[left],nums[right])));
                    left++;right--;
                    while (left < right && nums[left] == nums[left-1])left++;
                    while (left < right && nums[right] == nums[right+1]) right--;
                }else if (sum > -cur){
                    right--;
                }else {
                    left++;
                }
            }
            i++;
           while (i < len && nums[i] == nums[i-1])i++;
        }
        return ans;
    }
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n;) {
            //三数之和
            for (int j = i+1; j < n; ) {

                int left = j+1,right =n-1;
                long cur =(long) target-nums[i]-nums[j];//用long处理有可能溢出

                while (left < right){

                    long sum=(long)nums[left]+nums[right];
                    if (sum > cur){
                        right--;
                    }else if (sum < cur){
                        left++;
                    }else {
                        ans.add(new ArrayList<>(Arrays.asList(nums[i],nums[j],nums[left++],nums[right--])));

                        while (left < right && nums[left-1] == nums[left])left++;
                        while (left < right && nums[right+1] == nums[right])right--;
                    }
                }
                j++;
                while ( j<n && nums[j-1] == nums[j])j++;
            }
            i++;
            while (i<n && nums[i]==nums[i-1])i++;
        }
        return ans;
    }




}